﻿/************************************************************************
 * SMLib - State Model Library
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     SMLib\Automata\MM\MM_Generator.cs
 * Description  :     Generation of random Mealy machines
 * Change log   :     -Jan 2013:  Initial version
 * To Do        :     -add probability for output seclection
 *                    -make it as a static functiom
 ************************************************************************/
using System;
using System.Collections.Generic;
using SMLib.Automata.Base;

namespace SMLib.Automata.MM
{
	/// <summary>
	/// Generate a random -identifiable- Mealy machine
	/// <remarks></remarks>
	/// </summary>
	public class MM_Generator
	{
		/// <summary>
		/// Type of Generation Enum
		/// <remarks>
		/// In a random machine, destination of each transition is selected fully randomly where as
		/// in a balanced machine, it is random but still the generator tries to keep the machine balanced
		/// (i.e. all states have more or less same number of incomming transitions)
		/// </remarks>
		/// </summary>
		enum GenerationType
		{
			/// <summary>
			/// Fully random destination
			/// </summary>
			RANDOM,
			/// <summary>
			/// Balanced machine
			/// </summary>
			BALANCED
		}
		
		static GenerationType TypeOfGeneration= GenerationType.BALANCED;
		
		
		int numberOfStates;
		int numberOfBranchPoints;
		int branchDegree;
		string machineName;
		Random rng;
		
		/// <summary>
		/// It should be in [1..numberOfStates]
		/// </summary>
		int balancenessCoef = 3;

		/// <summary>
		/// Class constructor. Instead of using this class, you may directly use the static method "GenerateARandomMachine"
		/// </summary>
		/// <param name="numberOfStates">number of nodes (states) in the mealy machine</param>
		/// <param name="numberOfBranchPoints">number of nodes that have non-deterministic transitions</param>
		/// <param name="branchDegree">degree of nondeterminism (currently, just one)</param>
		private MM_Generator(string machineName, int numberOfStates, int numberOfBranchPoints, int branchDegree)
		{
			//* check the parameters
			if (machineName == null || machineName == "")
				throw new Exception("A machine should have a non-empty name!");
			if(numberOfStates<=0)
				throw new Exception("Number of states should be positive!");
			if(numberOfBranchPoints>numberOfStates)
				throw new Exception("Number of branches could not be greater than number of states!");
			else if(numberOfBranchPoints<0)
				throw new Exception("Number of branchs should be non-negative!");
			
			//* construct the generator
			this.numberOfBranchPoints = numberOfBranchPoints;
			this.numberOfStates = numberOfStates;
			this.branchDegree = branchDegree;
			this.machineName = machineName;
			rng = new Random();
		}


		/// <summary>
		/// Generate a random mealy machine (with/without nondeterminism)
		/// </summary>
		/// <param name="machineName">Name of machine</param>
		/// <param name="NumberOfStates">number of states</param>
		/// <param name="NumberOfBranch">number of branches (states which have non-deterministic transitions)</param>
		/// <param name="BranchDegree">Number of extra transitions in each branch node</param>
		/// <param name="inputSize">size of input alphabet</param>
		/// <param name="OutputSize">size of output alphabet</param>
		/// <returns>the generated machine</returns>
		public static MealyMachine GenerateARandomMachine(string machineName, int NumberOfStates, int NumberOfBranch, int BranchDegree,
		                                                  int inputSize = 3, int OutputSize = 3)
		{
			MM_Generator g =
				new MM_Generator(machineName, NumberOfStates, NumberOfBranch, BranchDegree);

			Alphabet inp = new Alphabet();
			for (int i = 0; i < inputSize; i++)
				inp.AddSymbol(new StringSymbol("i" + i));

			Alphabet outp = new Alphabet();
			for (int i = 0; i < OutputSize; i++)
				outp.AddSymbol(new StringSymbol("o" + i));

			return g.Generate(inp, outp);
		}

		
		MealyMachine.Mealy_State DestOf(MealyMachine.Mealy_State node, ISymbol input, ISymbol output)
		{
			foreach (object tr in node.Transitions)
			{
				MealyMachine.Mealy_Transition trs = (MealyMachine.Mealy_Transition)tr;
				if (trs.inLabel == input && trs.outLabel == output)
					return (MealyMachine.Mealy_State)trs.Destination;
			}
			return null;
		}

		MealyMachine.Mealy_State SelRandomDest(MealyMachine machine,List<int> incommingEdge)
		{
			MealyMachine.Mealy_State dest = null;
			int rndIndex;
			
			if (TypeOfGeneration == GenerationType.BALANCED)
			{
				// Find a node with minimum number of incomming edge
				int j,min = 0;
				int minValue = incommingEdge[0];

				
				List<int> minList = SMLib.Utils.SortUtil.Find(balancenessCoef, incommingEdge);
				minValue = minList[minList.Count - 1];
				int c = 0;
				// Count how many nodes are volunteered for destination
				for (j = 0; j < numberOfStates; j++)
				{
					if (incommingEdge[j] <= minValue)
						c++;
				}

				rndIndex = rng.Next(c);
				int c2 = 0;
				for (j = 0; j < numberOfStates; j++)
				{
					if (incommingEdge[j] <= minValue)
					{
						if (c2 == rndIndex)
						{
							min = j;
							break;
						}
						c2++;
					}
				}

				incommingEdge[min]++;
				dest = (MealyMachine.Mealy_State)machine[min];
			}
			else if (TypeOfGeneration == GenerationType.RANDOM)
			{
				// random policy
				rndIndex = rng.Next(numberOfStates);
				dest = (MealyMachine.Mealy_State)machine[rndIndex];
			}
			return dest;
		}
		
		/// <summary>
		/// Generate machine with the given parameters (in the construction time)
		/// </summary>
		/// <param name="inAlphabet">the input alphabet</param>
		/// <param name="outAlphabet">the output alphabet</param>
		/// <returns>the generated machine</returns>
		MealyMachine Generate(Alphabet inAlphabet, Alphabet outAlphabet)
		{
			if(inAlphabet==null || outAlphabet==null)
				throw new Exception("Input and output alphabet should be non-null!");
			
			if(inAlphabet.Size==0 || outAlphabet.Size==0)
				throw new Exception("Input and output alphabet should be non-empty!");
			
			MealyMachine machine = new MealyMachine();
			machine.InputAlphabet = inAlphabet;
			machine.OutputAlphabet = outAlphabet;

			// [To-Do]
			// 0: Just the middle non-determinism
			//int option2 = 0;


			int i, k;
			int rndIndex;
			List<int> incommingEdge = new List<int>();
			for (i = 0; i < numberOfStates; i++)
			{
				// Construct the empty machine
				machine.AddState(new MealyMachine.Mealy_State(machineName + i.ToString()));
				incommingEdge.Add(0);
			}

			#region Generate a balanced/deterministic/complete mealy machine
			for (i = 0; i < numberOfStates; i++)
			{
				//* For each input
				foreach (ISymbol s in inAlphabet.AllSymbols())
				{
					//* select a destination node
					MealyMachine.Mealy_State dest=SelRandomDest(machine,incommingEdge);
					
					//* Choose a random output
					rndIndex = rng.Next(outAlphabet.Size);
					ISymbol output = outAlphabet.AllSymbols()[rndIndex];

					//* Create a new transition for the input, for the random output AND for the selected destination
					MealyMachine.Mealy_Transition t = new MealyMachine.Mealy_Transition(s, output);
					t.SetDestination(dest);
					machine[i].Transitions.Add(t);
				}
			}
			#endregion

			#region Add some nondeterminism
			List<int> listOfBranches = new List<int>();
			for (i = 0; i < numberOfBranchPoints; i++)
			{
				//* Select a random source node
				rndIndex = rng.Next(numberOfStates);
				MealyMachine.Mealy_State srcNode = (MealyMachine.Mealy_State)machine[rndIndex];

				//* If we add some nondeterminism in this node before, skip this AND try again!
				if (listOfBranches.Contains(rndIndex))
				{
					//* try again
					i--;
					continue;
				}
				
				
				listOfBranches.Add(rndIndex);

				for (k = 0; k < branchDegree; k++)
				{
					//* now: select ONE random input (all nondeterministic transitions are in
					rndIndex = rng.Next(inAlphabet.Size);

					ISymbol input = inAlphabet.AllSymbols()[rndIndex];

					//* select a destination node
					MealyMachine.Mealy_State dest =SelRandomDest(machine,incommingEdge);
					
					//* Choose a random output [which doesn't make the machine "non-identifiable"]
					ISymbol output;
					do
					{
						rndIndex = rng.Next(outAlphabet.Size);
						output = outAlphabet.AllSymbols()[rndIndex];
					} while (DestOf(srcNode, input, output) != null);

					//* Create a new transition for the input, for the random output AND for the selected destination
					MealyMachine.Mealy_Transition t = new MealyMachine.Mealy_Transition(input, output);
					t.SetDestination(dest);
					srcNode.Transitions.Add(t);
				}
			}
			#endregion

			return machine;
		}
	}
}
